<?php

class Solution
{

    /**
     * @param Integer $n
     * @return String[]
     */
    function simplifiedFractions($n)
    {
        if ($n == 1) {
            return [];
        }
        $ret = [];
        for ($i = 2; $i <= $n; $i++) {
            for ($j = 1; $j < $i; $j++) {
                if ($this->gcd($i, $j) == 1) {
                    $ret[] = "$j/$i";
                }
            }
        }

        return $ret;
    }

    /**求最大公约数
     *
     * @param $a
     * @param $b
     * @return mixed
     */
    function gcd($a, $b)
    {
        while ($b > 0) {
            $c = $a % $b;
            $a = $b;
            $b = $c;
        }
        return $a;
    }
}
